package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

import java.util.ArrayList;

/**
 * 给定头节点，获得树上最大的搜索子树个数
 * <p>
 * 分情况讨论，最大搜索子树与当前头X是否有关系：
 * 1、与X无关，说明最大搜索子树出现在头X的左树或者右树上
 * 2、与X有关，说明最大搜索子树是以X为头的整棵树本身：
 * 此时需要满足：
 * 1、右子树最小值 > x节点值   >左子树max值
 * 2、左右子树都为搜索二叉树
 * 如果满足，那么最大搜索子树个数也自然为X为头树的高度
 */
public class Test09_GetMaxSubSearchTreeSize {

    public static int getMaxSubSearchTreeSize(Node node) {
        if (node == null) {
            return 0;
        }

        return process(node).maxSubSearchTreeSize;


    }

    public static TreeInfo process(Node node) {
        if (node == null) {
            return null;
        }

        TreeInfo leftInfo = process(node.left);
        TreeInfo rightInfo = process(node.right);


        int max = node.value;
        int min = node.value;
        int allSize = 1;

        int p1 = -1;//左树的最大搜索子树个数
        int p2 = -1;//右树的最大搜索子树个数
        int p3 = -1;//整棵树的最大搜索子树个数

        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            allSize += leftInfo.allSize;
            p1 = leftInfo.maxSubSearchTreeSize;
        }

        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            allSize += rightInfo.allSize;
            p2 = rightInfo.maxSubSearchTreeSize;
        }

        boolean leftSearchable = leftInfo == null || leftInfo.allSize == leftInfo.maxSubSearchTreeSize;
        boolean rightSearchable = rightInfo == null || rightInfo.allSize == rightInfo.maxSubSearchTreeSize;
        //左树是搜索二叉 && 右树是搜索二叉
        if (leftSearchable && rightSearchable) {
            boolean leftLess = leftInfo == null || leftInfo.max < node.value;
            boolean rightMore = rightInfo == null || rightInfo.min > node.value;
            if (leftLess && rightMore) {
                p3 = allSize;
            }
        }

        return new TreeInfo(Math.max(Math.max(p1, p2), p3), max, min, allSize);


    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (maxSubBSTSize1(head) != getMaxSubSearchTreeSize(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
//
//    public static void main(String[] args) {
//        Node node = new Node(30);
//        Node node2 = new Node(20);
//        Node node3 = new Node(40);
//        Node node4 = new Node(10);
//        Node node5 = new Node(25);
//        Node node6 = new Node(32);
//        Node node7 = new Node(60);
//        Node node8 = new Node(6);
//        Node node9 = new Node(13);
//
//        node.left = node2;
//        node.right = node3;
//        node2.left = node4;
//        node2.right = node5;
//        node3.left = node6;
//        node3.right = node7;
//        node4.left = node8;
//        node4.right = node9;
//
//         /*
//                   30
//             20              40
//           10    15         32     60
//         6   13
//
//         */
//
//        System.out.println(getMaxSubSearchTreeSize(node));
//    }

    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static int getBSTSize(Node head) {
        if (head == null) {
            return 0;
        }
        ArrayList<Node> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return 0;
            }
        }
        return arr.size();
    }

    public static void in(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    public static int maxSubBSTSize1(Node head) {
        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
    }

    static class TreeInfo {
        int maxSubSearchTreeSize;
        int max;
        int min;
        int allSize;

        public TreeInfo(int maxSubSearchTreeSize, int max, int min, int allSize) {
            this.maxSubSearchTreeSize = maxSubSearchTreeSize;
            this.max = max;
            this.min = min;
            this.allSize = allSize;
        }
    }


}
